716. Max Stack
Easy

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

  • MaxStack() Initializes the stack object.
  • void push(int x) Pushes element x onto the stack.
  • int pop() Removes the element on top of the stack and returns it.
  • int top() Gets the element on the top of the stack without removing it.
  • int peekMax() Retrieves the maximum element in the stack without removing it.
  • int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

  • -107 <= x <= 107
  • At most 104 calls will be made to push, pop, top, peekMax, and popMax.
  • There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 
Accepted
79,297
Submissions
181,996
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 3.42 (76 votes)

Approach #1: Two Stacks [Accepted]

Intuition and Algorithm

A regular stack already supports the first 3 operations, so we focus on the last two.

For peekMax, we remember the largest value we've seen on the side. For example if we add [2, 1, 5, 3, 9], we'll remember [2, 2, 5, 5, 9]. This works seamlessly with pop operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.

For popMax, we know what the current maximum (peekMax) is. We can pop until we find that maximum, then push the popped elements back on the stack.

Our implementation in Python will showcase extending the list class.

Complexity Analysis

  • Time Complexity: O(N)O(N) for the popMax operation, and O(1)O(1) for the other operations, where NN is the number of operations performed.

  • Space Complexity: O(N)O(N), the maximum size of the stack.


Approach #2: Double Linked List + TreeMap [Accepted]

Intuition

Using structures like Array or Stack will never let us popMax quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making popMax faster than O(N)O(N) time complexity.

Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in O(1)O(1) time.

We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in O(logN)O(\log N) time.

Algorithm

Let's store the stack as a double linked list dll, and store a map from value to a List of Node.

  • When we MaxStack.push(x), we add a node to our dll, and add or update our entry map.get(x).add(node).

  • When we MaxStack.pop(), we find the value val = dll.pop(), and remove the node from our map, deleting the entry if it was the last one.

  • When we MaxStack.popMax(), we use the map to find the relevant node to unlink, and return it's value.

The above operations are more clear given that we have a working DoubleLinkedList class. The implementation provided uses head and tail sentinels to simplify the relevant DoubleLinkedList operations.

A Python implementation was not included for this approach because there is no analog to TreeMap available.

Complexity Analysis

  • Time Complexity: O(logN)O(\log N) for all operations except peek which is O(1)O(1), where NN is the number of operations performed. Most operations involving TreeMap are O(logN)O(\log N).

  • Space Complexity: O(N)O(N), the size of the data structures used.

Report Article Issue

Comments: 61
begabtli's avatar
Read More

I don't think I can write 80 lines of code in the interview. So I will be the candidate who cannot find the optimal solution for an easy level question.​​

199
Show 5 replies
Reply
Share
Report
trungfun's avatar
Read More

Why this question is marked Easy? In my view, it is even harder than many Medium questions.

67
Reply
Share
Report
game_never_stop's avatar
Read More

Obviously, the first solution is more interview-friendly.

60
Show 5 replies
Reply
Share
Report
Liziyang1110's avatar
Read More

When you come up with an O(N) solution ( similar to the 1st solution) in an interview, it is likely to get a followed up question like "can you improve the performance?", so you will need to at least know how to use TreeMap to tackle this type of problem. After a few hints, you finally know you will use doubly linkedlist...In my mind, this is a at least Medium Difficulty level problem. But anyway, practice makes perfect. We really need to stop complaining but spend more time on more problems. cheers.

59
Reply
Share
Report
syed17's avatar
Read More

This should be a medium level question I believe, the explanation of the solution is very good. Thank You @awice for your contributions to the LC community.

23
Reply
Share
Report
secretcoder1988's avatar
Read More

In first Solution, I feel there is something wrong with popMax algorithm.
It will result in unequal number in maxStack in case of 3, 5, 1 as an input.

19
Show 1 reply
Reply
Share
Report
softwareshortcut's avatar
Read More

I think this problem is a very good exercise for interviews because it helps you showcase your time complexity skills and trade-offs versus spitting out the most optimized version. If a candidate tells me that the goal is to reduce the time complexity of popMax, that alone is a positive signal. If you manage to come up with solution 2 verbally, it's a very good signal. If you actually code solution 2 in 15 minutes, I'd know you've seen it on LC :)

11
Show 2 replies
Reply
Share
Report
kevinhynes's avatar
Read More

Approach #1 Python solution is broken. You cannot compare None with an int so the push method should be replaced with:

def push(self, x):
    m = max(x, self[-1][1] if self else float("-inf"))
    self.append((x, m))

But even then, the algorithm fails for input:

["MaxStack","push","push","popMax","peekMax"]
[[],[5],[1],[],[]]

Cmon, I thought this was an "easy" question!

9
Show 4 replies
Reply
Share
Report
zestypanda's avatar
Read More

How do you handle duplicates for approach 2?

4
Show 2 replies
Reply
Share
Report
pauru's avatar
Read More

First solution is wrong. push(5), push (1) and then popMax(), then maxstack is empty. Ideally maxstack should have value 1

8
Reply
Share
Report
Success
Details
Runtime: 68 ms, faster than 76.38% of C++ online submissions for Max Stack.
Memory Usage: 39.1 MB, less than 69.24% of C++ online submissions for Max Stack.
Time Submitted
Status
Runtime
Memory
Language
06/19/2021 09:26Accepted68 ms39.1 MBcpp
06/19/2021 09:23Accepted64 ms39.3 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.